Graph / Vertex cover (Bibtex)

P264: Enumeration of all minimal vertex covers in a graph

Input:

A graph $G = (V, E)$.

Output:

All minimal vertex covers of size up to $k$ in $G$.

Complexity:

$O^*(1.6181^k)$ total time.

Comment:

This algorithm also lists some non-minimal vertex covers. This algorithm uses compact representation technique.

Reference:

[Fernau2006] (Bibtex)

P267: Enumeration of all minimal vertex covers of size at most $k$ in a graph

Input:

A graph $G = (V, E)$.

Output:

All minimal vertex covers of size at most $k$ in $G$.

Complexity:

$O(|E| + k^2 2^k)$ total time.

Comment:

Reference:

[Damaschke2006] (Bibtex)